import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Locale;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
class FindElements {
    TreeNode newRoot;
    public FindElements(TreeNode root) {
        newRoot=root;
        newRoot.val=0;
        dfs(newRoot);
    }
    public boolean find(int target) {
        TreeNode cur=newRoot;
        if(state(cur,target)){
            return true;
        }
        return false;
    }
    public void dfs(TreeNode newRoot){
        if(newRoot==null){
            return;
        }
        if(newRoot.left!=null){
            newRoot.left.val=newRoot.val*2+1;
        }
        if(newRoot.right!=null){
            newRoot.right.val=newRoot.val*2+2;
        }
        dfs(newRoot.left);
        dfs(newRoot.right);
    }
    public boolean state(TreeNode root,int key){
        if(root==null){
            return false;
        }
        if(root.val==key){
            return true;
        }
        boolean left=state(root.left,key);
        boolean right=state(root.right,key);
        return left||right;
    }
}

















public class project {
    public String capitalizeTitle(String title) {
        String[] str=title.split(" ");
        StringBuilder sb=new StringBuilder();
        for(int i=0;i< str.length;i++){
            String s=str[i];
            int len=s.length();
            if(len<3){
                sb.append(s.toLowerCase());
            }else{
                sb.append(Character.toUpperCase(s.charAt(0)));
                sb.append(s.substring(1).toLowerCase());
            }
            if(i!=str.length-1){
                sb.append(" ");
            }
        }
        return sb.toString();
    }


























    public int[] sortEvenOdd(int[] nums) {
        int len=nums.length;
        int[] arr1=new int[len/2];
        int[] arr2=new int[len%2==1?len/2+1:len/2];
        int j=0;
        int k=0;
        int i=0;
        while (i<len){
            arr2[j]=nums[i++];
            if(i==len){
                break;
            }
            arr1[j]=nums[i++];
            j++;
        }
        Arrays.sort(arr1);
        Arrays.sort(arr2);
        j=arr1.length-1;
        k=0;
        i=0;
        while (i<len){
            nums[i++]=arr2[k++];
            if(i==len){
                break;
            }
            nums[i++]=arr1[j--];
        }
        return nums;
    }

















    public int findTheWinner(int n, int k) {
        if(n==1){
            return 1;
        }
        int ans=findTheWinner(n-1,k)+k;
        return ans%k==0?n:(ans%n);
    }














    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root==null){
            return new TreeNode(val);
        }
        add(root,val);
        return root;
    }
    public void add(TreeNode root,int val){
        if(root==null){
            return;
        }
        if(root.val<val){
            if(root.right==null){
                root.right=new TreeNode(val);
                return;
            }
            add(root.right,val);
        }else{
            if(root.left==null){
                root.left=new TreeNode(val);
                return;
            }
            add(root.left,val);
        }
    }












    public boolean checkString(String s) {
        int[] arr=new int[2];
        for(char ch : s.toCharArray()){
            arr[ch-'a']++;
        }
        for(int i=0;i<arr[0];i++){
            char ch=s.charAt(i);
            if(ch!='a'){
                return false;
            }
        }
        return true;
    }


















    int sum=0;
    public int distributeCoins(TreeNode root) {
        dfs(root);
        return sum;
    }
    public int dfs(TreeNode root){
        if(root==null){
            return 0;
        }
        int left=dfs(root.left);
        int right=dfs(root.right);
        sum+=Math.abs(left)+Math.abs(right);
        return root.val+left+right-1;
    }


















    TreeNode ret=null;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs1(root,p,q);
        return ret;
    }
    public boolean dfs1(TreeNode node,TreeNode p,TreeNode q){
        if(node==null){
            return false;
        }
        boolean leftState=dfs1(node.left, p, q);
        boolean rightState=dfs1(node.right,p,q);
        if((leftState&&rightState)||(node.val==p.val||node.val==q.val)&&(leftState||rightState)){
            ret=node;
        }
        return leftState||rightState||(node.val==q.val||node.val==p.val);
    }















    public String complexNumberMultiply(String num1, String num2) {
        String[] str1=num1.split("\\+|i");
        String[] str2=num2.split("\\+|i");
        int ax=Integer.parseInt(str1[0]);
        int ay=Integer.parseInt(str1[1]);
        int bx=Integer.parseInt(str2[0]);
        int by=Integer.parseInt(str2[1]);
        return (ax*bx-ay*by)+"+"+(ax*by+ay*bx)+"i";
    }










    public int minimumDifference(int[] nums, int k) {
        Arrays.sort(nums);
        int min=Integer.MAX_VALUE;
        int len=nums.length;
        for(int i=0;i<len-k+1;i++){
            min=Math.min(min,nums[len+i-1]-nums[i]);
        }
        return min;
    }
}
